package com.leetcode.No1234;

import org.junit.Test;

/**
 * @program: leetcode
 * @description: 替换子串得到平衡字符串
 * @author: wangzhihua
 * @date: 2021-06-21
 */
public class Solution01 {

	@Test
	public void test() {
//		System.out.println(balancedString("WWEQERQWQWWRWWERQWEQ"));
		System.out.println(balancedString("QQQE"));
	}

	private int averageSum;
	private final int q = 'Q' - 'A';
	private final int w = 'W' - 'A';
	private final int e = 'E' - 'A';
	private final int r = 'R' - 'A';

	public int balancedString(String s) {
		int[] initNum = new int[30];
		int[] num = new int[30];

		int sum = s.length();
		this.averageSum = sum >> 2;

		for (int i = 0; i < s.length(); ++i) {
			++initNum[s.charAt(i) - 'A'];
		}
		if (check(initNum)) {
			return 0;
		}

		// 滑块的初始长度
		int len = Math.max(initNum[q] - averageSum, 0)
				+ Math.max(initNum[w] - averageSum, 0)
				+ Math.max(initNum[e] - averageSum, 0)
				+ Math.max(initNum[r] - averageSum, 0);

		while(len < s.length()) {
			num[q] = 0;
			num[w] = 0;
			num[e] = 0;
			num[r] = 0;

			// 滑块范围[left, right)
			int left = 0, right = len;

			for (int i = right; i < s.length(); ++i) {
				++num[s.charAt(i) - 'A'];
			}

			do {
				if (check(num)) {
					return len;
				}
				++num[s.charAt(left++) - 'A'];
				--num[s.charAt(right++) - 'A'];
			} while (right < s.length());
			if (check(num)) {
				return len;
			}

			++len;
		}

		return len;
	}

	private boolean check(int[] array) {
		return array[q] <= averageSum
				&& array[w] <= averageSum
				&& array[e] <= averageSum
				&& array[r] <= averageSum;
	}

}
